Lehmer's GCD algorithm
FAST GREATEST COMMON DIVISOR ALGORITHM DEVELOPED BY LEHMER
Lehmer's algorithm; Lehmer GCD algorithm
Lehmer's GCD algorithm, named after Derrick Henry Lehmer, is a fast GCD algorithm, an improvement on the simpler but slower Euclidean algorithm. It is mainly used for big integers that have a representation as a string of digits relative to some chosen numeral system base, say β = 1000 or β = 232.